Data Representation and Boolean Algebra

In a positional number system the value of a digit depends on its face value (the digit itself) and its place value (its position, expressed as a power of the base). The total number of unique digits is the base or radix.

Binary (base 2), decimal (10), octal (8) and hexadecimal (16). Computers use binary because their circuits are built from transistors that have two states: high (ON) = 1 and low (OFF) = 0. Octal and hexadecimal are shorthand for long binary numbers; decimal is used for interaction with users.

Base 10, digits 0–9.

5398 = 5×10³ + 3×10² + 9×10¹ + 8×10⁰ = 5000 + 300 + 90 + 8.

385.76 = 3×10² + 8×10¹ + 5×10⁰ + 7×10⁻¹ + 6×10⁻² = 300 + 80 + 5 + 0.7 + 0.06.

The digit with the highest place value is the Most Significant Digit (MSD, leftmost); the lowest is the Least Significant Digit (LSD, rightmost).

Base 2, with digits 0 and 1; each digit is a bit (binary digit). The leftmost bit is the Most Significant Bit (MSB) and the rightmost the Least Significant Bit (LSB). Numbers like 10111 or 110011 also exist in decimal, so the base is written as a subscript, e.g. (10111)₂, in all systems except decimal.

(11010)₂ = 1×16 + 1×8 + 0×4 + 1×2 + 0×1 = 26.

Base 16 with symbols 0–9 and A–F; each hex digit corresponds to 4 bits (2⁴ = 16), so it is a compact way of writing binary.

(10A)₁₆ = 1×16² + 0×16¹ + 10×16⁰ = 256 + 0 + 10 = 266.

Divide repeatedly by 2 until the quotient is 0, note the remainders, and write them in reverse order.

29: 29÷2 → 14 r1; 14÷2 → 7 r0; 7÷2 → 3 r1; 3÷2 → 1 r1; 1÷2 → 0 r1. Reading upward: 29 = (11101)₂.

Divide repeatedly by 16, replace remainders 10–15 by A–F, and read the remainders in reverse.

381 ÷ 16 = 23 r 13 (D); 23 ÷ 16 = 1 r 7; 1 ÷ 16 = 0 r 1. So 381 = (17D)₁₆.

Multiply each bit by its power of 2 (rightmost = 2⁰) and add.

(101101)₂ = 32 + 0 + 8 + 4 + 0 + 1 = 45.

Group bits in fours from the right, padding the leftmost group with zeros, and replace each group by its hex symbol.

1101001011 → 0011 0100 1011 → (34B)₁₆.

Replace each hex digit by its 4-bit binary equivalent and join.

(7B0D)₁₆ = 0111 1011 0000 1101 = (0111101100001101)₂.

Start from the LSB and add the carry to the next column. 1 + 1 + 1 gives sum 1 and carry 1. A final carry becomes the MSB. Examples: 1001 + 101 = 1110; 101101 + 10011 = 1000000.

When 1 is subtracted from 0, a 1 is borrowed from the next higher bit; the 0 then becomes 10 (decimal 2) and the difference is 1. Examples: 1101 – 1001 = 0100; 101000 – 10111 = 10001.

Data representation is expressing data (numbers, text, images, audio, video) in binary form that a computer can understand. A word is a fixed-size group of bits processed by the processor; its number of bits is the word length (commonly 8, 16, 32 or 64). This chapter uses 8 bits.

Sign and magnitude, 1's complement and 2's complement.

The MSB is the sign bit (0 positive, 1 negative); the remaining 7 bits hold the magnitude.

+25: 25 = 11001 → 7 bits 0011001 → sign 0 → (00011001)₂.

–109: 109 = 1101101 (7 bits) → sign 1 → (11101101)₂.

A positive number is written in normal binary; a negative number is obtained by inverting all bits of its positive form.

+92 = (01011100)₂. –92: invert 01011100 → (10100011)₂.

A positive number is written in normal binary; a negative number = 1's complement + 1.

+75 = (01001011)₂. –75: 1's complement 10110100, add 1 → (10110101)₂.

For –78: magnitude 78 = 01001110; sign and magnitude sets the MSB to 1; 1's complement inverts to 10110001; 2's complement adds 1.

Sign and magnitude and 1's complement have two zeros (+0 and –0), which wastes a pattern; 2's complement has a single zero and can represent one extra number (–4), eliminating the negative-zero problem. The same hardware can add and subtract positive and negative numbers.

1. Pad the subtrahend with zeros to equal length.
2. Find its 1's complement.
3. Add it to the minuend.
4. If there is a carry out of the MSB, add it to the LSB of the sum (end-around carry).

1's complement of 1001 = 0110. 1101 + 0110 = 1 0011 (carry 1). Add the carry: 0011 + 1 = 0100.

1. Pad the subtrahend.
2. Find its 2's complement.
3. Add it to the minuend.
4. Ignore any carry out of the MSB.

1's complement of 1001 = 0110; add 1 → 0111. 1101 + 0111 = 1 0100; ignore the carry → 0100.

Method for (a) with 2's complement: pad 1101 to 01101; its 2's complement is 10011; 10011 + 10011 = 1 00110; ignoring the carry gives 00110 = 110.

It stores real numbers (with a fractional part) that may be extremely large or small, e.g. 3.14, 0.00045, 2500000.0. The binary point "floats" left or right depending on the size of the number, like scientific notation, so a wide range of values can be stored in a fixed number of bits. Example: 1011.11 = 1.01111 × 2³.

±(1.mantissa) × 2^exponent. Parts: sign bit (0 positive, 1 negative), exponent (position of the binary point) and mantissa (the digits of the number). Example: (101.01)₂ = 1.0101 × 2².

Because only a limited number of bits are available, some decimal fractions cannot be stored exactly, causing tiny rounding errors.

Computers understand only 0s and 1s, so each character gets a unique bit pattern through a standard code. ASCII (American Standard Code for Information Interchange) was developed in the early 1960s; each character has a unique integer (ASCII code) stored in binary. Original ASCII used 7 bits = 128 characters (0–127): control characters (0–31), printable characters (32–126: letters, digits, punctuation, symbols) and DEL (127). Extended ASCII uses 8 bits = 256 characters, adding graphic symbols and accented letters.

A universal standard that assigns a unique number (code point) to every character of all languages, overcoming the limits of ASCII, EBCDIC and ISCII. It originally used 16 bits (65,536 characters) and now covers over 1,00,000 characters, including symbols and emojis.

• UTF-8: variable size, 1–4 bytes; compatible with ASCII; most widely used on the Internet (web pages, email, URLs).
• UTF-16: 16 bits per character.
• UTF-32: 32 bits per character.

The developer and ISCII details are from general knowledge; the chapter itself gives the full forms, bit sizes and ranges for ASCII and UTF-8.

An image is stored as a grid of tiny dots called pixels, each with a binary colour value. Resolution is the number of pixels (width × height, e.g. 1920 × 1080); more pixels give better quality. Colour depth is the number of bits per pixel: 8-bit gives 256 colours; 24-bit gives about 16 million colours.

Bitmap (raster): made of pixels in rows and columns, e.g. photographs and scans. Vector: made of mathematical shapes (lines, curves), resolution-independent and can be resized without losing quality, e.g. logos and diagrams.

Formats: BMP, JPEG, PNG, GIF, TIFF, WEBP, HEIF/HEIC and SVG (vector).

Analog sound waves are converted to digital form (digitisation) by measuring the wave at regular time intervals. Each measurement is a sample; the number of samples per second is the sampling rate (44.1 kHz = 44,100 samples per second for music); the number of bits per sample is the bit depth. Higher values give better quality but need more storage. Formats: WAV, AIFF (uncompressed), MP3, WMA, AAC (compressed).

A video is a sequence of image frames shown quickly (24–30 per second) with digital audio. Quality depends on frame rate (fps; higher = smoother), resolution (pixels per frame) and bit rate (data per second; higher = better quality but larger file). Because videos are large, they are compressed using codecs (coder-decoder). Formats: AVI, MP4, MOV, WMV, MKV.

A branch of mathematics that works with two values, 1 (true) and 0 (false), using the operations AND, OR and NOT. Developed by George Boole. It is used to design digital circuits and switching systems, to control hardware logic, and in programming for conditions, loops and comparisons.

A truth table lists all possible input combinations and the output for a logical operation or circuit. With m operands and n operators it needs 2^m rows and m + n columns.

An electronic circuit that performs a specific logical operation on one or more input signals. Gates are the building blocks of microprocessors, memory units and control circuits.

OR is logical addition, written A + B. Output is 1 if any input is 1. Electrically, two switches in parallel with a bulb: the bulb glows if either switch is closed.

AND is logical multiplication, written A . B. Output is 1 only when all inputs are 1. Electrically, two switches in series with a bulb: the bulb glows only when both are closed.

NOT is a unary operator (one input) that gives the opposite value; written A or A'. The NOT gate is also called an inverter.

Example: an automatic night lamp. In daylight the sensor input is 1 and the lamp is off (0); at night the input is 0 and the lamp turns on (1).

The output is 1 when B = 1 and at least one of A or C is 1.

Every Boolean expression has a dual obtained by (i) changing each + to ., (ii) changing each . to +, and (iii) replacing each 0 by 1 and each 1 by 0 (variables are left as they are). If an expression evaluates to 0, its dual evaluates to 1 and vice versa. For example, A + A' = 1 always, so its dual A . A' = 0 always.

Complemented variables stay complemented in the dual.

If two expressions give the same output for every input combination, they are equivalent, and writing E1 = E2 is a Boolean identity. A truth table with columns A, B, C, B+C, A.(B+C), A.B, A.C, A.B+A.C gives identical columns for A.(B+C) and A.B+A.C (output 1 only for ABC = 101, 110, 111). This is the Distributive law.

• A + 0 = A
• A . 1 = A
• A . 0 = 0
• A + 1 = 1

The first two are dual to each other, and so are the last two.

(i) (A + B)' = A' . B' – the complement of a sum is the product of the complements.
(ii) (A . B)' = A' + B' – the complement of a product is the sum of the complements.

The last two columns are identical, proving the theorem. The second theorem is proved the same way with A . B and (A . B)' against A' + B'.

The printed table has lost its complement bars in the text, so here are the standard identities it covers, each verifiable by a truth table:

Circuit design converts a Boolean expression into a combination of logic gates (AND, OR, NOT) connected to perform the required function. Using Boolean identities to simplify the expression first reduces the number of gates and connections, making the circuit cheaper, more efficient and easier to build.

S2 and S3 feed a 2-input OR gate. The output of the OR gate and S1 feed a 2-input AND gate; the AND output is the bulb B. The bulb glows when the main switch S1 is ON and at least one of S2 or S3 is ON.

The sprinkler is ON when S1 = 1, S2 = 1 and S3 = 0 (not raining):

Sprinkler = S1 . S2 . S3'

Circuit: S3 goes through a NOT gate; its output, S1 and S2 feed a 3-input AND gate (or two 2-input AND gates in sequence). The AND output drives the sprinkler.

The alarm sounds when the power is ON and either the door or the window is open:

Alarm = S1 . (S2 + S3)

Circuit: S2 and S3 feed an OR gate; its output and S1 feed an AND gate whose output is the alarm.

(a) A.B + A.C: two AND gates (A with B, and A with C); their outputs feed one OR gate. Three gates in all. By the distributive law it equals A.(B + C), which needs only an OR gate followed by an AND gate (two gates).

(c) (A + B).(A + C): two OR gates (A with B, and A with C); their outputs feed one AND gate. By the distributive law this equals A + B.C, which needs only an AND gate followed by an OR gate.

For expressions with complemented variables, such as B.C' or A'.C, add a NOT gate on that input before the AND gate.

Any other gate (AND, OR, NOT) can be built using only NAND gates or only NOR gates, so they are universal gates. Using a single type of gate means fewer different components, easier manufacture, lower cost, better use of IC space, and simpler testing and fault detection.

NAND = AND followed by NOT: (A.B)'. Output is 0 only when all inputs are 1. NOR = OR followed by NOT: (A+B)'. Output is 1 only when all inputs are 0. Both need at least two inputs.

• NOT: connect A to both inputs: (A.A)' = A'.
• AND: a NAND gate followed by a NAND used as an inverter: ((A.B)')' = A.B.
• OR: invert each input with a NAND (as NOT), then feed both to a NAND gate: (A'.B')' = A + B (De Morgan).

• NOT: connect A to both inputs: (A+A)' = A'.
• OR: a NOR gate followed by a NOR used as an inverter: ((A+B)')' = A + B.
• AND: invert each input with a NOR, then feed both to a NOR gate: (A'+B')' = A . B.

Using NAND only (5 gates): n1 = NAND(B, B) = B'; n2 = NAND(C, C) = C'; n3 = NAND(n1, n2) = B + C; n4 = NAND(A, n3); output = NAND(n4, n4) = A.(B + C).

Using NOR only (3 gates): n1 = NOR(B, C) = (B + C)'; n2 = NOR(A, A) = A'; output = NOR(n2, n1) = (A' + (B+C)')' = A.(B + C).

All three output columns match, so the circuits are correct.

• Base of the hexadecimal system: 16; bits per hex digit: 4.
• Bits in original ASCII: 7 (128 characters); extended ASCII: 8 (256).
• Sign bit for a negative number: 1.
• Representation with only one zero: 2's complement.
• Gate that inverts its input: NOT (inverter).
• Gate whose output is 1 only when all inputs are 1: AND.
• Universal gates: NAND and NOR.
• Number of rows in a truth table with 3 variables: 8 (2³).
• Boolean algebra was developed by: George Boole; De Morgan's theorems by Augustus De Morgan.